#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class MinPrice:
    RAW_VALUE = -1
    next_color = [
        (1, 2),
        (0, 2),
        (0, 1)
    ]

    def __init__(self):
        self.house_price = [
            [100, 77, 73],
            [41, 74, 83],
            [9, 91, 93],
            [50, 16, 31],
        ]


        self.n = len(self.house_price)

        self.init_memory()

    def init_memory(self):
        one_line = 3 * [self.RAW_VALUE]

        # HINT: self.memory : 一个 (n+1) * 3的 矩阵/二维数组, 用来查表, 空间换时间
        self.memory = [list(one_line) for i in range(self.n+1)]

        # HINT: 初始化递归边界
        for color_idx in range(3):
            self.memory[self.n][color_idx] = 0

    def min_house(self):
        self.min_house_loop_build()
        return min(self.memory[0])

    def min_house_loop_build(self):
        # 从第n-1所房子开始到第0所房子, 逆着构建最优化解
        for house_idx in range(self.n-1, -1, -1):
            for color_idx in range(3):
                color1 = self.next_color[color_idx][0]
                color2 = self.next_color[color_idx][1]

                cur_price = self.house_price[house_idx][color_idx]

                min_price = cur_price + min(self.memory[house_idx+1][color1], self.memory[house_idx+1][color2])

                self.memory[house_idx][color_idx] = min_price

def test():
    m = MinPrice()
    p = m.min_house()
    print(p)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
